package com.chapter2.sort;

/** 
 * @ClassName: SelectionAlgorithums 
 * @Description: 选择算法（从数组中选择第k小的元素）
 * 
 *  可以利用先排序再查找的方式，这样最简单。但是效率不是最高的，没必要对所有数组排序，可以直接利用快排的切分思想寻找第k小的元素，这样可以达到线性的时间复杂度
 * @author minjun minjun@bw30.com
 * @date 2015-2-16 下午5:35:48 
 *  
 */
public class SelectionAlgorithums {
	
	private Shuffle shuffle;
	
	private Swapable swapable;
	
	public SelectionAlgorithums() {
		shuffle=new ShuffleImpl();
		swapable=new SwapImpl();
	}

	public int select(int[] array,int k){
		//要切分之前首先'洗牌'，这样可以得到更高的执行效率
		shuffle.randomShuffle(array);
		int start=0;
		int end=array.length-1;
		while(start<=end){
			int m=partition(array,start,end);
			if(k<m) end=m-1;
			else if(k>m) start=m+1;
			else return array[m];
		}
		throw new RuntimeException("找不到该元素");
	}

	/** 
	* @Title: partition 
	* @Description: 切分
	* @param @param array
	* @param @param start
	* @param @param end
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws 
	*/ 
	private int partition(int[] array, int start, int end) {
		int i=start;
		int j=end+1;
		
		while(true){
			while(array[++i]<array[start]){
				if(i>=end) break;
			}
			
			while(array[--j]>array[start]){
				if(i<=0) break;
			}
			
			if(i>=j) break;
			
			swapable.exchange(array, i, j);
		}
		
		swapable.exchange(array, j, start);
		
		return j;
	}
}
